package solutions.leetcode.normal

/**
 * @author lizhidong
 * <a href="https://leetcode.cn/problems/3sum/">15. 三数之和</a>
 */
class Solution15 {
    fun threeSum(nums: IntArray): List<List<Int>> {
        val rst = ArrayList<List<Int>>()
        if (nums.size <= 2) {
            return rst
        }
        nums.sort()
        var i = 0
        while (i < nums.size - 2) {
            var l = i + 1
            var r = nums.size - 1
            while (l < r) {
                val sum = nums[l] + nums[r] + nums[i]
                if (sum > 0) {
                    r--
                } else if (sum < 0) {
                    l++
                } else {
                    rst.add(arrayOf(nums[i], nums[l], nums[r]).toList())
                    while (l < r) {
                        l++
                        if (nums[l - 1] != nums[l]) {
                            break
                        }
                    }
                    while (l < r) {
                        r--
                        if (nums[r + 1] != nums[r]) {
                            break
                        }
                    }
                }
            }
            while (i < nums.size - 2) {
                i++
                if (nums[i - 1] != nums[i]) {
                    break
                }
            }
        }
        return rst
    }
}

fun main() {
    println(
        Solution15().threeSum(
            arrayOf(
                -1, -1, -1, 2, 2
            ).toIntArray()
        )
    )
}